1. Field of the Invention
The present invention relates to binary adders for integrated circuits. Specifically, the present invention relates to carry look ahead adders in which propagation delay and hardware costs are minimized.
2. Discussion of the Related Art
FIG. 1 illustrates a standard ripple carry adder structure. The ripple carry adder takes two binary numbers, A and B, as inputs, and produces a single binary number, S, as output. In the example shown in FIG. 1, A, B, and S are each six bits in length. The ripple carry adder in FIG. 1 is made of six full adder cells 100. Although the ripple carry adder is implemented with a minimal amount of hardware, its propagation delay is relatively large. Each full adder 100 takes a carry input C.sub.in which is necessary to compute its sum output and carry output C.sub.out. The amount of time necessary for the most significant bit S.sub.5 of the output S and the carry output C.sub.6 to become valid is constrained by the possibility of an asserted carry signal rippling through the row of adders from C.sub.0 to C.sub.6. If each full adder cell 100 requires a time t.sub.c to compute the C.sub.out output after the C.sub.in input has become valid, then the total propagation delay of the adder shown in FIG. 1 is 6*t.sub.c. Generally, the propagation delay is approximately n*t.sub.c for a ripple carry adder, where n is the number of full adders in the circuit. Therefore, the growth of the propagation delay of the ripple carry adder is a linear function of the number of bits in the addends.
The linear growth of a ripple carry adder's propagation delay is improved by calculating the carries to each stage in parallel with the sum computations for that stage. Carry look ahead is a technique for reducing the carry propagation delay by computing the output carry signal for several bits in parallel with the sum computations for those same bits. FIG. 2 shows the structure of a 6-bit carry look ahead adder. The 6-bit adder in FIG. 2 has two stages 200 and 201 of three-level look ahead circuits. Each three-level look ahead circuit 200 and 201 directly computes its C.sub.out output based upon the appropriate six bits of the addends--three bits from A and three bits from B--and its carry input C.sub.in. A carry look ahead adder is typically designed so that the latency of the computation of C.sub.out after its C.sub.in input becomes valid has the same order of latency as each full adder cell 203. In this manner, the full adder cells 204 computing the more significant bits of the adder's output receive their carry inputs earlier than in a similar ripple carry adder so that the most latent outputs, S.sub.5 and C.sub.6, become valid with less latency.
In order to implement a carry look ahead circuit, the carry output C.sub.i from the i.sup.th level is written in terms of the necessary inputs required for its computation. The carry output from the i.sup.th level, C.sub.i, can be expressed as follows. EQU C.sub.i =G.sub.i +P.sub.i .multidot.C.sub.i-1 ( 1)
where EQU G.sub.i =A.sub.i .multidot.B.sub.i ( 2)
and EQU P.sub.i =A.sub.i +B.sub.i ( 3)
Here, G.sub.i is the generate signal, which indicates that the addition of A.sub.i and B.sub.i will generate a carry output from the i.sup.th full adder. P.sub.i is the propagate signal, which indicates that any carry input to the i.sup.th full adder cell will be propagated to the carry output.
By recursive substitution, the carry output of the i.sup.th level, C.sub.i, can be written as: EQU C.sub.i =G.sub.i +P.sub.i .multidot.G.sub.i-1 +P.sub.i P.sub.i-1 .multidot.G.sub.i-2 + . . . +P.sub.i . . . P.sub.1 .multidot.C.sub.0( 4)
For three levels of look ahead, each carry look ahead circuit implements the following equation: EQU C.sub.out =G.sub.2 +P.sub.2 .multidot.G.sub.1 +P.sub.2 .multidot.P.sub.1 .multidot.G.sub.0 +P.sub.2 .multidot.P.sub.1 .multidot.P.sub.0 .multidot.C.sub.in ( 5)
There is a limit to the timing benefit which can be achieved by using a large carry look ahead circuits. When the number of levels of look ahead becomes too large, the number of inputs to the gates necessary to compute the outputs increases such that the delay through the carry look ahead circuit becomes disproportionately large. Thus, there is a limit to the speed improvement which can be achieved from the use of carry look ahead techniques.
The amount of hardware necessary to implement m stages of a k-level carry look ahead circuit is always less than the amount of hardware necessary to implement a single stage of k*m-level carry look ahead circuit. This inequality is a result of the fact that the complexity of the computation of C.sub.out increases polynomially as k increases. Therefore, the amount of hardware necessary to make a k-level carry look ahead circuit can clearly get out of hand when k becomes too large. As a result, the number of levels of look ahead is usually limited to about six.
One way to implement a carry look ahead circuit with very little delay through the critical path from carry in to carry out is the carry add select circuit. In the carry add select circuit, as shown in FIG. 3, two separate carry computation circuits 300 and 301 are used to speculatively calculate both possible carry outputs C.sub.out0 and C.sub.out1 based upon the two possible carry input values, zero or one. The advantage to this approach is that the speculative computations of the two possible carry outputs C.sub.out0 and C.sub.out1 begin before the carry input C.sub.in 302 has been computed by the preceding look ahead stage. When the preceding look ahead stage has computed its output, which is the carry input 302 of the present look ahead stage, the correct output 303 is selected from among the two speculatively computed possibilities. C.sub.out0 and C.sub.out1, by the multiplexor 304. Therefore, the propagation delay for the carry look ahead stage is merely the delay from the select input 305 to the output 303 of the multiplexor. Any given multiplexor implementation requires at least two logic levels; therefore, a minimum of two gate delays are required to implement a multiplexor. A multiplexor circuit employs either two inverting gates or two transmission gates. FIGS. 4A and 4B show two alternative implementations of the multiplexor 304 shown in FIG. 3. Either implementation has substantially larger delays than a single inverting gate.
For a k-bit carry look ahead adder circuit, the fundamental Equation 4 can be written in the following form. EQU C.sub.k =G+P.multidot.C.sub.0 ( 6)
where EQU P=P.sub.k . . . P.sub.1 ( 7)
and EQU G=G.sub.k +P.sub.k .multidot.G.sub.k-1 +P.sub.k .multidot.P.sub.k-1 .multidot.G.sub.k-2 + . . . +P.sub.k . . . P.sub.2 .multidot.G.sub.1( 8)
C.sub.k is the carry output of the k-bit carry look ahead adder circuit, while C.sub.0 is the carry input. Previous implementations of a carry look ahead circuit preserve the polarity from the carry input C.sub.0, to the carry output C.sub.k, as indicated in Equation 6. In other words, both the carry input C.sub.0 and the carry output C.sub.k are represented using positive logic according to the prior art.
FIGS. 5A and 5B show typical logic circuits which performs the computation of C.sub.k from C.sub.0, P, and G as described by Equation 6. Similar to the carry add select circuit, the typical logic circuit shown in FIGS. 5B attempt to minimize the delay from the input C.sub.0 to the output C.sub.k. Depending upon the number of levels of look ahead (k), the generation of P and G can become complex computations involving only k bits of A and k bits of B, but not involving carry information from previous stages. Therefore, the computations of P and G in any given carry look ahead stage begin immediately, and are designed so as to finish before C.sub.0 becomes valid, so that the path from C.sub.0 to C.sub.k is the critical path. The logic implementation shown in FIG. 5B clearly requires two gate delays.